#include <omp.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>

using namespace std;

// aufgabe 8
// erstellt Liste aller Primzahlen kleiner N
int main(int argc, char* argv[]) {


    const int N =1000000;
    int i,j,n_threads;
    bool prim[N];
    int max=1;
    double comp_start, comp_end;

    printf( "Anzahl der threads=?");
    fflush(stdout);
    scanf("%d", &n_threads);

    omp_set_num_threads(n_threads);
    omp_set_dynamic(0);

    #pragma omp parallel for shared (prim)
    for (i=0;i<N;i++){
        prim[i]=true;
    }

    comp_start=omp_get_wtime();

    #pragma omp parallel for shared (prim)
    for ( i =2; i< (int) sqrt ((double) N ); i++){

        if ( prim[i]){

            #pragma omp parallel for shared (prim)
            for ( j=2*i; j<N; j+=i){
                //#pragma omp critical // dieses critical zerstoert leider alle Parallelitaet!
                prim [j]= false ;
            }
        }
    }



    comp_end=omp_get_wtime();
    printf( "\nCPU-time used is: %f\n",(comp_end-comp_start));

    #pragma omp parallel for
    for ( int i=0; i<N; i++){
        if (prim[i] && (i>max)) max=i;
    }

    printf( "groesste Primzahl= %d \n", max);

    return 0;

}
